package com.leo.datastruct.sort;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月02日
 */
public class RadixSort extends Sortable {

    public RadixSort(String sortMethodName) {
        super(sortMethodName);
    }

    @Override
    public void sort(int[] s) {
        int exp;
        int max = max(s);
        for (exp = 1; max/exp> 0 ; exp*=10) {
            radixSort(s, exp);
        }
    }

    private void radixSort(int[] s, int exp) {
        int[] output = new int[s.length];
        int[] buckets = new int[10];

        // 将数据出现的次数存储在buckets[]中
        for (int i = 0; i < s.length; i++) {
            buckets[(s[i] / exp) % 10]++;
        }

        // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
        for (int i = 1; i < 10; i++) {
            buckets[i] += buckets[i - 1];
        }

        // 将数据存储到临时数组output[]中
        for (int i = s.length - 1; i >= 0; i--) {
            output[buckets[ (s[i]/exp)%10 ] - 1] = s[i];
            buckets[ (s[i]/exp)%10 ]--;
        }

        // 将排序好的数据赋值给s[]
        for (int i = 0; i < s.length; i++){
            s[i] = output[i];
        }
    }

    /**
     * 获取数组最大值
     * @param s
     * @return
     */
    private int max(int[] s){
        int max = s[0];
        for (int i = 1; i < s.length; i++) {
            if (max < s[i]) { max = s[i]; }
        }
        return max;
    }

    public static void main(String[] args) {
        Sortable a = new RadixSort("基数排序");
        a.testSort(new int[]{49,38,65,97,76,13,27,49,78,34,12,64,1});
    }
}
